#include"BinaryTree.h"
#include<limits>
#include<vector>
#include<stack>
namespace dzh{
	template<class T>
	struct BTNode
	{
		BTNode(const T& val)
			:_val(val)
		{
		}
		T _val = T();
		shared_ptr<BTNode> _left = nullptr;
		shared_ptr<BTNode> _right = nullptr;
	};

	template<class T>
	class BinaryTree
	{
	public:
		BinaryTree(list<string> preOrderData)
		{
			//使用槽位法进行前序序列是否能够正确构建二叉树的判断
			int cnt = 1;
			for(const auto& e : preOrderData)
			{
				if(e == "N")
				{
					--cnt;
				}
				else
				{
					++cnt;
				}
				assert(cnt >= 0);
			}
			assert(cnt == 0);
			
			CreateTree(_head, preOrderData);	
		}
		BinaryTree(const BinaryTree& other)
		{
			_Copy(_head, other._head);
			_size = other._size;
		}
		BinaryTree operator=(BinaryTree other)//使用惯用法
		{
			_swap(*this, other);
			return *this;
		}
		//使用unique_ptr，且另一成员变量为内置类型，因此无需实现析构函数
		//~BinaryTree()
		//{
		//}
		void CreateTree(shared_ptr<BTNode<T>>& head, list<string>& preOrderData)
		{
			if(preOrderData.front() == "N")
			{
				preOrderData.pop_front();//当遇到空字符时，也要记得pop
				return;
			}
			head = (make_shared<BTNode<T>>(preOrderData.front()));
			preOrderData.pop_front();
			CreateTree(head->_left, preOrderData);
			CreateTree(head->_right, preOrderData);
			++_size;	
		}
		void PreOrder()
		{
			_PreOrder(_head);
			cout << endl;
		}
		void InOrder()
		{
			_InOrder(_head);
			cout << endl;
		}
		void PostOrder()
		{
			_PostOrder(_head);
			cout << endl;
		}
		size_t CountDegree0Nodes()
		{
			return _CountDegree0Nodes(_head);
		}
		size_t CountDegree1Nodes()
		{
			//这里一定要注意，最好不要使用static进行计数，因为类示例化出的所有对象都共用一个函数，而因此，函数中的静态变量也就被共用了，而static在计算后必须进行清零操作，否则在自身或其他对象再次计算时，结果将是错误的
			shared_ptr<size_t> p1(make_shared<size_t>(0));
			_CountDegree1Nodes(_head, p1);
			return *p1;
		}
		size_t CountDegree2Nodes()
		{
			shared_ptr<size_t> p2(make_shared<size_t>(0));
			_CountDegree2Nodes(_head, p2);
			return *p2;
		}
		void NodePath(const string pos)
		{
			vector<string> vs;
			vs = _NodePath(pos, _head, vs);
			if(vs.empty())
			{
				cout << "二叉树中不存在该节点！" << endl;
				return;
			}
			cout << "该节点的路径为：" << endl;
		//	for(const auto& e : vs)
		//	{
		//		cout << e << " ";
		//	}
			for(auto i = vs.begin(); i != vs.end(); ++i)
			{
				if(i == --vs.end())
				{
					cout << *i;
				}
				else
				{
					cout << *i << "->";
				}
			}
		}
		size_t GetSize()
		{
			return _size;
		}
		bool IsEmpty()
		{
			return _size == 0;
		}
	private:
		shared_ptr<BTNode<T>> _head = nullptr;//有在Create函数递归过程中unique无法拷贝的担忧
		size_t _size = 0;
		void _PreOrder(shared_ptr<BTNode<T>>& head)
		{
			if(head == nullptr)
			{
				cout << 'N' << " ";
				return;
			}
			cout << head->_val << " ";
			_PreOrder(head->_left);
			_PreOrder(head->_right);
		}
		void _InOrder(shared_ptr<BTNode<T>>& head)
		{
			if(head == nullptr)
			{
				cout << 'N' << " ";
				return;
			}
			_InOrder(head->_left);
			cout << head->_val << " ";
			_InOrder(head->_right);
		}
		void _PostOrder(shared_ptr<BTNode<T>>& head)
		{
			if(head == nullptr)
			{
				cout << 'N' << " ";
				return;
			}
			_PostOrder(head->_left);
			_PostOrder(head->_right);
			cout << head->_val << " ";
		}
		size_t _CountDegree0Nodes(shared_ptr<BTNode<T>>& head)
		{
			if(head == nullptr)
			{
				return 0;
			}
			else if(head->_left == nullptr && head->_right == nullptr)
			{
				return 1;
			}
			else
			{
				return _CountDegree0Nodes(head->_left) + _CountDegree0Nodes(head->_right);
			}
		}
		void _CountDegree1Nodes(shared_ptr<BTNode<T>>& head, shared_ptr<size_t> p1)
		{
			if(head == nullptr)
			{
				return;
			}
			if((head->_left && !head->_right) || (!head->_left && head->_right))
			{
				++(*p1);
			}
			_CountDegree1Nodes(head->_left, p1);
			_CountDegree1Nodes(head->_right, p1);
		}
		void _CountDegree2Nodes(shared_ptr<BTNode<T>>& head, shared_ptr<size_t> p2)
		{
			if(head == nullptr)
			{
				return;
			}
			if(head->_left && head->_right)
			{
				++(*p2);
			}
			_CountDegree2Nodes(head->_left, p2);
			_CountDegree2Nodes(head->_right, p2);
		}

		vector<string> _NodePath(string pos, shared_ptr<BTNode<T>>& head, vector<string> vs)
		{
			if(head == nullptr)
			{
				return vector<string>();
			}
			if(head->_val == pos)
			{
				vs.emplace_back(pos);
				return vs;
			}
			vs.emplace_back(head->_val);
			vector<string> vs1 = _NodePath(pos, head->_left, vs);
			vector<string> vs2 = _NodePath(pos, head->_right, vs);
			if(!vs1.empty() && vs1.back() == pos)
			{
				return vs1;
			}
			if(!vs2.empty() && vs2.back() == pos)
			{
				return vs2;
			}
			return vector<string>();
		}
		//使用前序遍历的方法进行copy操作，但这里需要稍微注意下，由于拷贝构造中传递的是const &类型的other，所以，其中的成员变量也是不允许更改的，因此，_Copy的参数要使用const&
		void _Copy(shared_ptr<BTNode<T>>& head, const shared_ptr<BTNode<T>>& otherHead)
		{
			if(otherHead == nullptr)
			{
				return;
			}
			head = make_shared<BTNode<T>>(otherHead->_val);
			_Copy(head->_left, otherHead->_left);
			_Copy(head->_right, otherHead->_right);
		}
		void _swap(BinaryTree& t1, BinaryTree& t2)
		{
			std::swap(t1._head, t2._head);
			std::swap(t1._size, t2._size);
		}
	};

	void test1()
	{
		list<string> lt;
		string line = "";
		if(getline(cin, line))
		{
			string mid = "";
			for(const auto& e : line)
			{
				if(e != ' ')
				{
					mid.push_back(e);
				}else
				{
					lt.emplace_back(mid);
					mid = "";
				}
			}
			//输入最后一个数据后会直接回车，即最后一个数据后没有' ',因此需要在最后一个数据时进行特殊处理，不过用户也有可能直接输入回车，因此还需要判断一下mid当前是否为空
			if(!mid.empty())
			{
				lt.emplace_back(mid);
			}
		}
		BinaryTree<string> bt(lt);
		bt.PreOrder();
		bt.InOrder();
		bt.PostOrder();
		cout << bt.CountDegree0Nodes() << endl;
		cout << bt.CountDegree1Nodes() << endl;
		cout << bt.CountDegree2Nodes() << endl;
		BinaryTree<string> bts = bt;
		bts.PreOrder();
		bts.InOrder();
		bts.PostOrder();
		cout << bts.CountDegree0Nodes() << endl;
		cout << bts.CountDegree1Nodes() << endl;
		cout << bts.CountDegree2Nodes() << endl;
	}
	void Display()
	{
            cout << "\n========== 二叉树测试菜单 ==========\n";
            cout << "1. 创建二叉树\n";
            cout << "2. 前序遍历\n";
            cout << "3. 中序遍历\n";
            cout << "4. 后序遍历\n";
            cout << "5. 统计度数为0的节点数\n";
            cout << "6. 统计度数为1的节点数\n";
            cout << "7. 统计度数为2的节点数\n";
            cout << "8. 显示所有统计信息\n";
            cout << "9. 拷贝二叉树\n";
			cout << "10. 显示单个节点的路径\n";
            cout << "0. 退出\n";
            cout << "请选择操作: ";
	}

	void TestFinal()
    {
        shared_ptr<BinaryTree<string>> currentTree = nullptr;
        string s = "";
		int choice = 0;//如果直接使用int类型+cin接收，用户输入字符类型时会改变cin的状态位，同时，该int类型的值可能不变，此为bug，我的修复策略为，索性使用string类型接收，这样可以接收基本所有的内置类型，然后，使用stoi将stirng转换int，即可得到正确结果，而且stoi转换失败会抛异常，相当方便
        do
        {
			Display();
            cin >> s;
			try{
				choice = stoi(s);
			}
			catch(const std::invalid_argument& errid)
			{
				cout << "输入的是非int类型数据！" << endl;
				choice = -1;
			}
			catch(const std::out_of_range& errid)
			{
				cout << "输入的数字过大！" << endl;
				choice = -1;
			}
            // 清除输入缓冲区，防止错误输入影响后续操作
            cin.ignore(numeric_limits<streamsize>::max(), '\n');

            // 使用switch处理用户选择
            switch (choice)
            {
                case 1:
                {
                    list<string> lt;
                    string line = "";
                    cout << "请输入二叉树的前序遍历序列（用空格分隔，空节点用'N'表示）: ";
                    if (getline(cin, line))
                    {
                        string mid = "";
                        for (const auto& e : line)
                        {
                            if (e != ' ')
                            {
                                mid.push_back(e);
                            }
                            else
                            {
                                if (!mid.empty())
                                {
                                    lt.emplace_back(mid);
                                    mid = "";
                                }
                            }
                        }
                        if (!mid.empty())
                        {
                            lt.emplace_back(mid);
                        }
						currentTree = make_shared<BinaryTree<string>>(lt);
                        cout << "二叉树创建成功！总节点数: " << currentTree->GetSize() << endl;
                    }
                    break;
                }

                case 2:
                {
                    if (currentTree != nullptr && !currentTree->IsEmpty())
                    {
                        cout << "前序遍历结果: ";
                        currentTree->PreOrder();
                    }
                    else
                    {
                        cout << "错误：请先创建二叉树！" << endl;
                    }
                    break;
                }

                case 3:
                {
                    if (currentTree != nullptr && !currentTree->IsEmpty())
                    {
                        cout << "中序遍历结果: ";
                        currentTree->InOrder();
                    }
                    else
                    {
                        cout << "错误：请先创建二叉树！" << endl;
                    }
                    break;
                }

                case 4:
                {
                    if (currentTree != nullptr && !currentTree->IsEmpty())
                    {
                        cout << "后序遍历结果: ";
                        currentTree->PostOrder();
                    }
                    else
                    {
                        cout << "错误：请先创建二叉树！" << endl;
                    }
                    break;
                }

                case 5:
                {
                    if (currentTree != nullptr && !currentTree->IsEmpty())
                    {
                        size_t count = currentTree->CountDegree0Nodes();
                        cout << "度数为0的节点数（叶子节点）: " << count << endl;
                    }
                    else
                    {
                        cout << "错误：请先创建二叉树！" << endl;
                    }
                    break;
                }

                case 6:
                {
                    if (currentTree != nullptr && !currentTree->IsEmpty())
                    {
                        size_t count = currentTree->CountDegree1Nodes();
                        cout << "度数为1的节点数: " << count << endl;
                    }
                    else
                    {
                        cout << "错误：请先创建二叉树！" << endl;
                    }
                    break;
                }

                case 7:
                {
                    if (currentTree != nullptr && !currentTree->IsEmpty())
                    {
                        size_t count = currentTree->CountDegree2Nodes();
                        cout << "度数为2的节点数: " << count << endl;
                    }
                    else
                    {
                        cout << "错误：请先创建二叉树！" << endl;
                    }
                    break;
                }

                case 8:
                {
                    if (currentTree != nullptr && !currentTree->IsEmpty())
                    {
                        cout << "=== 二叉树统计信息 ===" << endl;
                        cout << "总节点数: " << currentTree->GetSize() << endl;
                        cout << "度数为0的节点数: " << currentTree->CountDegree0Nodes() << endl;
                        cout << "度数为1的节点数: " << currentTree->CountDegree1Nodes() << endl;
                        cout << "度数为2的节点数: " << currentTree->CountDegree2Nodes() << endl;

                        size_t sum = currentTree->CountDegree0Nodes() +
                                    currentTree->CountDegree1Nodes() +
                                    currentTree->CountDegree2Nodes();
                        cout << "验证（0度+1度+2度节点数）: " << sum << endl;
                    }
                    else
                    {
                        cout << "错误：请先创建二叉树！" << endl;
                    }
                    break;
                }

                case 9:
                {
                    if (currentTree != nullptr && !currentTree->IsEmpty())
                    {
                        auto newTree = make_shared<BinaryTree<string>>(*currentTree);
                        cout << "二叉树拷贝成功！" << endl;
                        cout << "原二叉树前序遍历: ";
                        currentTree->PreOrder();
                        cout << "新二叉树前序遍历: ";
                        newTree->PreOrder();
                        currentTree = newTree;
                        cout << "已切换到新二叉树。" << endl;
                    }
                    else
                    {
                        cout << "错误：请先创建二叉树！" << endl;
                    }
                    break;
                }
				case 10:
				{
					string pos;
					cout << "请输入需要查询的节点：" << endl;
					cin >> pos;
					currentTree->NodePath(pos);
					break;
				}
                case 0:
                {
                    cout << "感谢使用二叉树测试程序，再见！" << endl;
                    break;
                }

                default:
                {
                    cout << "错误：无效的选择，请重新输入！" << endl;
                    break;
                }
            }

        } while (choice != 0); // 当用户选择0时退出循环[6,7](@ref)
    }
}
